home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Atari Mega Archive 1
/
Atari Mega Archive - Volume 1.iso
/
gnu
/
gas
/
src138.zoo
/
hash.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-01-21
|
30KB
|
982 lines
/* hash.c - hash table lookup strings -
Copyright (C) 1987 Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
GAS is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 1, or (at your option)
any later version.
GAS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GAS; see the file COPYING. If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
/*
* BUGS, GRIPES, APOLOGIA etc.
*
* A typical user doesn't need ALL this: I intend to make a library out
* of it one day - Dean Elsner.
* Also, I want to change the definition of a symbol to (address,length)
* so I can put arbitrary binary in the names stored. [see hsh.c for that]
*
* This slime is common coupled inside the module. Com-coupling (and other
* vandalism) was done to speed running time. The interfaces at the
* module's edges are adequately clean.
*
* There is no way to (a) run a test script through this heap and (b)
* compare results with previous scripts, to see if we have broken any
* code. Use GNU (f)utilities to do this. A few commands assist test.
* The testing is awkward: it tries to be both batch & interactive.
* For now, interactive rules!
*/
/*
* The idea is to implement a symbol table. A test jig is here.
* Symbols are arbitrary strings; they can't contain '\0'.
* [See hsh.c for a more general symbol flavour.]
* Each symbol is associated with a char*, which can point to anything
* you want, allowing an arbitrary property list for each symbol.
*
* The basic operations are:
*
* new creates symbol table, returns handle
* find (symbol) returns char*
* insert (symbol,char*) error if symbol already in table
* delete (symbol) returns char* if symbol was in table
* apply so you can delete all symbols before die()
* die destroy symbol table (free up memory)
*
* Supplementary functions include:
*
* say how big? what % full?
* replace (symbol,newval) report previous value
* jam (symbol,value) assert symbol:=value
*
* You, the caller, have control over errors: this just reports them.
*
* This package requires malloc(), free().
* Malloc(size) returns NULL or address of char[size].
* Free(address) frees same.
*/
/*
* The code and its structures are re-enterent.
* Before you do anything else, you must call hash_new() which will
* return the address of a hash-table-control-block (or NULL if there
* is not enough memory). You then use this address as a handle of the
* symbol table by passing it to all the other hash_...() functions.
* The only approved way to recover the memory used by the symbol table
* is to call hash_die() with the handle of the symbol table.
*
* Before you call hash_die() you normally delete anything pointed to
* by individual symbols. After hash_die() you can't use that symbol
* table again.
*
* The char* you associate with a symbol may not be NULL (0) because
* NULL is returned whenever a symbol is not in the table. Any other
* value is OK, except DELETED, #defined below.
*
* When you supply a symbol string for insertion, YOU MUST PRESERVE THE
* STRING until that symbol is deleted from the table. The reason is that
* only the address you supply, NOT the symbol string itself, is stored
* in the symbol table.
*
* You may delete and add symbols arbitrarily.
* Any or all symbols may have the same 'value' (char *). In fact, these
* routines don't do anything with your symbol values.
*
* You have no right to know where the symbol:char* mapping is stored,
* because it moves around in memory; also because we may change how it
* works and we don't want to break your code do we? However the handle
* (address of struct hash_control) is never changed in
* the life of the symbol table.
*
* What you CAN find out about a symbol table is:
* how many slots are in the hash table?
* how many slots are filled with symbols?
* (total hashes,collisions) for (reads,writes) (*)
* All of the above values vary in time.
* (*) some of these numbers will not be meaningful if we change the
* internals.
*/
/*
* I N T E R N A L
*
* Hash table is an array of hash_entries; each entry is a pointer to a
* a string and a user-supplied value 1 char* wide.
*
* The array always has 2 ** n elements, n>0, n integer.
* There is also a 'wall' entry after the array, which is always empty
* and acts as a sentinel to stop running off the end of the array.
* When the array gets too full, we create a new array twice as large
* and re-hash the symbols into the new array, then forget the old array.
* (Of course, we copy the values into the new array before we junk the
* old array!)
*
*/
#include <stdio.h>
#define TRUE (1)
#define FALSE (0)
#include <ctype.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#include "hash.h"
char *xmalloc();
#define DELETED ((char *)1) /* guarenteed invalid address */
#define START_POWER (11) /* power of two: size of new hash table *//* JF was 6 */
/* JF These next two aren't used any more. */
/* #define START_SIZE (64) / * 2 ** START_POWER */
/* #define START_FULL (32) / * number of entries before table expands */
#define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
/* above TRUE if a symbol is in entry @ ptr */
#define STAT_SIZE (0) /* number of slots in hash table */
/* the wall does not count here */
/* we expect this is always a power of 2 */
#define STAT_ACCESS (1) /* number of hash_ask()s */
#define STAT__READ (0) /* reading */
#define STAT__WRITE (1) /* writing */
#define STAT_COLLIDE (3) /* number of collisions (total) */
/* this may exceed STAT_ACCESS if we have */
/* lots of collisions/access */
#define STAT_USED (5) /* slots used right now */
#define STATLENGTH (6) /* size of statistics block */
#if STATLENGTH != HASH_STATLENGTH
Panic! Please make #include "stat.h" agree with previous definitions!
#endif
/* #define SUSPECT to do runtime checks */
/* #define TEST to be a test jig for hash...() */
#ifdef TEST /* TEST: use smaller hash table */
#undef START_POWER
#define START_POWER (3)
#undef START_SIZE
#define START_SIZE (8)
#undef START_FULL
#define START_FULL (4)
#endif
/*------------------ plan ---------------------------------- i = internal
struct hash_control * c;
struct hash_entry * e; i
int b[z]; buffer for statistics
z size of b
char * s; symbol string (address) [ key ]
char * v; value string (address) [datum]
boolean f; TRUE if we found s in hash table i
char * t; error string; "" means OK
int a; access type [0...n) i
c=hash_new () create new hash_control
hash_die (c) destroy hash_control (and hash table)
table should be empty.
doesn't check if table is empty.
c has no meaning after this.
hash_say (c,b,z) report statistics of hash_control.
also report number of available statistics.
v=hash_delete (c,s) delete symbol, return old value if any.
ask() NULL means no old value.
f
v=hash_replace (c,s,v) replace old value of s with v.
ask() NULL means no old value: no table change.
f
t=hash_insert (c,s,v) insert (s,v) in c.